|
Projektbeschreibung:
In der Forschungsgruppe NEXUS wird eine offene Plattform für
Location Based Services entwickelt. Durch die Offenheit können
beliebige Datenanbieter ihre Daten durch die Plattform
bereitstellen. Eine Föderations-Middleware soll die Verteilung der
Daten vor einer Anwendung verbergen und die Daten verschiedener
Anbieter in geeigneter Weise kombinieren.
Zur Beschleunigung des Zugriffs auf die Daten werden an
verschiedenen Stellen der Plattform bereits Indexstrukturen
eingesetzt: im räumlichen Verzeichnisdienst, bei der Verwaltung von
Ergebnismengen oder bei der Verwaltung des Cache-Inhalts. Bisher
sind diese Indexe jedoch immer nur auf ein Attribut eines Objekts
bezogen. Typischerweise filtern Anfragen sowohl nach dem Ort eines
Objekts als auch nach dessen Typ, so dass in dieser Arbeit
untersucht werden soll, wie ein kombinierter Index aus Position und
Typ eines Objekts erstellt werden kann, und wie groß die
Effizienzsteigerungen dadurch sind.
Aufgabenstellung:
Ausgehend von bekannten Indexstrukturen für 1-D Daten (Binärbaum,
B*-Baum, ...) und 2-D Daten (R*-Baum, Quad-Tree, ...) soll als Basis
für weitere Vergleiche ein kombinierter Index entwickelt werden,
der entweder einen bekannten 1-D bzw. 2-D Index verwendet, um
Kandidaten zu ermitteln, welche anschließend von Hand in den noch
fehlenden Dimensionen gefiltert werden. Alternativ können auch
Kandidaten aus getrennten 1-D und 2-D Indexen ermittelt werden. Die
Schnittmenge der Kandidaten stellt dann das Endergebnis dar. Die
Typen der Objekte sind hierbei in einer baum-artigen Hierarchie ohne
Mehrfachvererbung angeordnet. Die Typen werden entweder in den |R1
abgebildet, oder es wird ein speziell auf diskrete hierarchische
Wertebereiche zugeschnittener Index eingesetzt. Anschließend soll
ein kombinierter Index entwickelt werden, bei dem Position und Typ
als Vektor bzw. ausgedehntes Objekt im 3-D Raum repräsentiert sind.
Dieser kombinierte Index soll mit den zuvor entwickelten
Basis-Varianten sowohl bezüglich der Anfragezeiten als auch der
Aktualisierungszeiten verglichen werden.
In einer zweiten Phase soll die Typ-Hierarchie um Mehrfachvererbung
erweitert und die kombinierte Indexstruktur entsprechend angepasst
werden. Es sollen verschiedene Alternativen für diese Anpassung
erarbeitet und analysiert werden. Im Ausblick kann aufgezeigt
werden, wie auch eine Level-of-Detail-Dimension oder eine
Zeit-Dimension in einen kombinierten Index integriert werden
können.
|